match(a,t).
match(t,a).
match(g,c).
match(c,g).
    
paired([],[]).
paired([X|L],[Y|G]) :- match(X,Y) , paired(L,G).
  
mismatches(L,G,R) :- misaux(L,G,R,1).
misaux([],[],[],_) :- !.
misaux([X|L],[Y|G],R,N) :- match(X,Y) , ! , M is N+1 , misaux(L,G,R,M).
misaux([_|L],[_|G],[N|R],N) :- M is N+1 , misaux(L,G,R,M).
   
repair(L,D,B,R) :- repaux(L,D,B,R,1).
repaux(L,[],_,L,_) :- !.
repaux([_|L],[N|D],[B1|B],[B1|R],N) :- !, M is N+1, repaux(L,D,B,R,M).
repaux([X|L],D,B,[X|R],N) :- M is N+1, repaux(L,D,B,R,M).
    
generate(0,[]) :- !.
generate(N,[X|L]) :- (X=a ; X=c ; X=g ; X=t) , P is N-1 , generate(P,L).

fitness([],_,0).
fitness([H|L1], L,N) :- mismatches(H,L,R) , length(R,X) , fitness(L1,L,M) , N is M+X.

    
fitaux(L,N,(G,S)) :- generate(N,G) , fitness(L,G,S).
findmin([(G,S)],(G,S)) :- !.
findmin([(G,S)|L],(G,S)) :- findmin(L,(_,S1)), S<S1.
findmin([(_,S)|L],(G1,S1)) :- findmin(L,(G1,S1)) , S1=<S.
fittest(L,N,G,S) :- bagof(T,fitaux(L,N,T),R) , findmin(R,(G,S)).


move(N,M) :- (N>1, M is N-2) ; (N>2, M is N-3) ; (N>3, M is N-4).
    
gagne2(N) :- (N mod 6)>1.